\section{Introduccion}
	
	Dada una red de amistades y dos investigadores (p-q), el problema consistia en ver cuanto se reducia el entusiasmo por cada relaci\'on por la que se pasa para llegar de p hasta q.
Para ello se decidi\'o implementar el ejercicio sobre grafos, donde cada investigador representado como vertice se conectaba con otro, generando de esta manera las relaciones entre los mismos.
Finalmente teniendo el grafo armado, la soluci\'on consisti\'o en buscar el camino mas corto de p a q (pasar por la menor cantidad de vertices).
	
\section{Desarrollo}

Para la resoluci\'on del ejercicio se utilizo la funcion $run$ (definida en la clase RED), la cual recibe tres parametros. Las dos primeras entradas son los nombres de los investigadores de los cuales se quiere resolver el problema, mientras que la tercera define las relaciones de la red, implementada sobre un vector de Amistad, donde $Amistad$ es una clase definida y basicamente es una tupla de Strings, a la cual se le puede pedir la primera o segunda componente, quedando de esta manera definida una relaci\'on entre 2 investigadores.\\
Esta funci\'on consta de tres parte principales:\\
La primera es generar un vector con todos los investigadores. Para ello se recorre una ves las relaciones de amistad (recibida por parametro), y se van agregando las mismas al vector.
La segunda, consiste en generar un grafo con todas las relaciones, implementada sobre una lista de adyacencias (se asocia a cada nodo del grafo una lista que contiene todos aquellos nodos que son adyacentes a el), representado por un Vector<Relaciones>.
El paso final es realizar una busqueda en anchura (Breadth First Search).Definici\'on :  Intuitivamente, se comienza en la raiz (eligiendo algun nodo como elemento raiz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuaci\'on para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y asi hasta que se recorra todo el arbol.
\begin{center}
Idea de la Listas de adyacencia 

 \includegraphics[width=15cm]{prob2/graficos/Listas_de_adyacencia.png}
\end{center}

\subsection{Pseudoc\'odigo}
Para una mejor explicacion se fragmento el ejercicio en tres partes.

\begin{algorithm}
PARTE 1: Generando vector de investigadores
\begin{algorithmic}[1]\parskip=1mm
\STATE   \textbf{var} investigadores $\leftarrow$ new Vector<String>
\IF{tamano(amistades) == 0}
\STATE return 0
\ENDIF
\FOR{ i = 0 \textbf{hasta} tamano(amistades)}
	\IF{! primero de $amistades$[i] esta en $investigadores$}
		\STATE  $investigadores$.add(primero de $amistades$[i])
	\ENDIF
	\IF{! segundo de $amistades$[i] esta en $investigadores$}
		\STATE  $investigadores$.add(segundo de $amistades$[i])
	\ENDIF
\ENDFOR
\end{algorithmic}
Complejidad: O($amistades.size()$ x 2 $investigadores.size()$)\\
%\end{algorithm}

%\begin{algorithm}
PARTE 2: Generando Grafo
\begin{algorithmic}[1]\parskip=1mm
\STATE   \textbf{var} grafo $\leftarrow$ Vector<Relaciones>
\FOR{ i = 0 \textbf{hasta} tamano(investigadores)}
	\STATE   \textbf{var} inv $\leftarrow$ investigadores[i]
	\STATE   $grafo$.add(i,Relaciones.Nuevo(inv,0,0))
	\FOR{ j = 0 \textbf{hasta} tamano(amistades)}
		\IF{$inv$ == primero(amistades[j])}
			\STATE  (hijos($grafo$[i])).add(segundo($amistades$[j]))
		\ENDIF
		\IF{$inv$ == segundo(amistades[j])}
			\STATE  (hijos($grafo$[i])).add(primero($amistades$[j]))
		\ENDIF
	\ENDFOR
\ENDFOR
\end{algorithmic}
Complejidad: O($investigadores.size()$ x $amistades.size()$)\\ 
%\end{algorithm}

%\begin{algorithm}
PARTE 3: Busqueda en el grafo. BuscarResultado($p$,$q$,$i$,grafo $G$) 
\begin{algorithmic}[1]\parskip=1mm
\STATE   $G$[i].modFlag(1)
\STATE   \textbf{var} path $\leftarrow$ Cola.Nuevo()
\STATE   path.Encolar($G$[i])
\WHILE{! vacio de $path$}
	\STATE   \textbf{var} nodo $\leftarrow$ path.Desencolar()
	\IF{nombre($nodo$) == $p$}
			\STATE  return altura($nodo$)
	\ENDIF
	\IF{tamano($nodo$.hijos()) != 0}
		\FOR{ j = 0 \textbf{hasta} $j$ < tamano($nodo$.hijos())}
			\STATE   \textbf{var} posicion $\leftarrow$ buscarString($nodo$.hijos()[j],$G$)
			\IF{($G$[posicion]).visitado() == 0}
				\STATE  ($G$[posicion]).visitado(1)
				\STATE  ($G$[posicion]).altura($nodo$.altura() + 1)
				\STATE  $path$.Encolar($G$[posicion])
			\ENDIF
		\ENDFOR
	\ENDIF
\ENDWHILE
\end{algorithmic}
Complejidad : O( ($|amistades|$ x $|investigadores|$ + $|investigadores|$))\\
\end{algorithm}


\subsection{Demostracion de complejidad}
%2-Justificar por que el procedimiento explicado en el primer punto resuelve efectivamente el problema.
La complejidad del algoritmo consiste principalmente en las tres partes explicadas con anterioridad.\\
La PARTE 1 consiste en recorrer todas las relaciones definidas para el sistema y por cada una de ellas preguntar si el investigador est\'a definido en el vector que me voy armando. Por lo tanto la complejidad de dicho algoritmo es 
de O(2 |relaciones| x |investigadores|), son dos veces las $relaciones$ ya que una relaci\'on se define como una tupla (2 investigadores) por lo tanto para cada relacion hay que recorrer dos veces la cantidad de investigadores en el peor caso.\\
La PARTE 2 tiene complejidad O(|investigadores| x |relaciones|), para cada investigador definido en la PARTE 1 (vector de investigadores) se le buscan las amistades (vector de tuplas de investigadores), para eso se va armando un grafo de relaciones, el cual consiste en agarrar un investigador $p$ (del vector investigadores) y buscarlo en las relaciones (vector amistades), una ves encontrado $p$, se agrega su relacion a la lista (hijos).\\

La PARTE 3 tiene complejidad  O( ($|amistades|$ x $|investigadores|$ + $|investigadores|$)). Se toma la lista de adyacencias que se genero en la PARTE 2  y se implementa una busqueda a lo ancho sobre el mismo.Dicho vector cuenta con un tamano que va a estar definido por la cantidad de investigadores.
Luego cada investigador va a tener su lista de hijos, los cuales representan las relaciones que el mismo tiene con los demas. De manera que el total de hijos definidos en la lista va a ser igual a la cantidad de relaciones que se hallan definido.
Como primer paso paso a buscar la posicion donde se encuentra el investigador que se quiere analizar ($q$),el cual tiene una complejidad de O(|investigadores|), para eso utilizo la funcion $buscarString$ (la comparacion de string es tomado como acotada).Una ves encontrado, se procede a recorrer sus hijos (acordarce que los mismos son las relaciones) en busca del investigador $p$. El procedimiento consiste en agarrar los hijos y ver si son el investigador buscado, si es, devuelvo la altura del nodo, caso contrario por cada hijo, le busco sus respectivos hijos en el vector de investigadores (buscarString) y los encolo, y asi sucesivamente hasta encontrar $p$.
Por lo tanto por cada relacion (hijos), busco el investigador , pido sus hijos y los encolo, teniendo una complejidad de O(|relaciones| * |investigadores|).
Para evitar los casos de ciclos, una ves que se paso por un nodo (investigador), este se lo marca como visitado, de esta manera si llego a un vertice que entre sus hijos se encuentra un nodo que tiene el FLAG en visitado, no se lo toma en cuenta para la busqueda de sus hijos, ya que esa relaci\'on fue analizada.\\
Finalmente sumando las complejidades tomo el m\'aximo de las mismas dando el total de O(|relaciones| x |investigadores|), ya que la suma de las complejidades es el m\'aximo de las mismas (por propiedad) y el dos al ser una constante puede ser despreciada.

\subsection{Casos de prueba de complejidad}
%8-Dar un conjunto de casos de test que permitan observar la performance en t´rminos de tiempo del problema. Para esto se deben desarrollar tanto tests patol´gicos de peor caso como tests generados sin una intencionalidad.

Para este problema decidimos separarlo en dos partes. La primera fue analizar la cantidad de iteraciones que se utilizaban para poder generar el grafo, y la segunda contar cuantas veces iteramos para realizar la busqueda del resultado en el grafo.
Es por eso que vamos a usar dos tipos de test.En primer termino vamos a ver como es la variacion de cantidad de operaciones basicas modificando los parametros de entrada, es decir agregando mas investigadores o relaciones de amistades.En esta parte del algoritmo no hay un peor caso, sino que la complejidad es exactamente recorrer todos los investigadores y por cada uno de estos recorrer todas las relaciones definidas, por lo tanto al incrementar los elementos de entrada se tendria que ver que los resultados son lineales con relacion a la entrada.
Para el segundo test si vamos a analizar el peor caso, que sucede cuando las relaciones se encuentran definidos como amigos todos los investigadores entre si (todos son amigos de todos).
Vamos a usar estos dos casos para ver que la complijidad teorica calculada mas arriba efectivamente se cumple de forma practica. 


\section{Resultados}
%9-Presentar en forma de gr´fico la comparaci´n entre tiempo estimado de corrida seg´n la complejidad temporal calculada, tiempo medido de corrida para los tests patol´gicos de peor caso, y tiempo medido de corrida para los tests sin intencionalidad.


\begin {center}
\includegraphics[width=12cm]{prob2/graficos/grafico1.png}\\
Comparacion entre variacion de los elementos de entrada para generar el grafo
\end {center}
Este gr\'afico nos muestra como varia la cantidad de iteraciones del for, para poder generar el grafo (que consiste en recorrer por cada investigador todas las relaciones definidas).
El caso que usamos para poder analizar la complejidad definida anteriormente fue ir variando la cantidad de elementos de la entrada y dejando la otra fija, para eso se definio 3 casos:
\begin{itemize}
\item investigador fijo: se establecio la cantidad de 15 investigadores, y varia la cantidad de relaciones.
\item relacion fijo: se establecio la cantidad de 15 relaciones, y varia la cantidad de investigadores.
\item variables: se va incrementando ambas variables en la misma cantidad.
\end{itemize}
Se decidio establecer uno de los parametros fijos para apreciar mejor como se comportaba la otra variable, ademas hay que tener en cuenta que una depende de la otra, es decir que no pueden tomar cualquier valor, ambas dependen de si. Por ejemplo si tengo 2 investigadores la cantidad maxima de relaciones posibles son 4 y si se definen como maximo 4 relaciones, la cantidad de investigadores no secesariamente son 2. Es por eso que no se dejo al azar la cantidad de los elementos de entrada, ya que podrian darce casos que son imposibles de realizar.
Viendo un poco el gr\'afico, nos damos cuenta que  las dos primeras relaciones son iguales es decir que cada una depende linealmente de la otra, (si se deja fijo los investigadores, la complejidad va a estar dada por las relaciones, lo mismo pasa en caso contrario).Para el tercero se observa que variando los investigadores y las relaciones en la misma cantidad la cantidad de iteraciones que se efectuan van a estar dadas por la multiplicacion de los investigadores y las relaciones.
 
\begin {center}
\includegraphics[width=12cm]{prob2/graficos/grafico2.png}\\
Gr\'afico del peor, ramdom y mejor caso para realizar la busqueda en el grafo
\end{center}

Este gr\'afico nos muestra la cantidad de iteraciones necesarias para recorrer el grafo en busqueda del resultado. Para ello se analizo el mejor caso (que seria realizar 3 operaciones basicas en caso que el resultado a buscar se encuentre como primer hijo entre p y q).
Para los casos promedio, se realizaron corridas, cuyas entradas fueron generadas variando aleatoriamente sus par\'ametros y se corrobor\'o que el tiempo de las mismas se encuentra entre los tiempos del mejor y del peor caso.
Por ultimo el peor caso esta dado cuando el resultado a buscar se encuentra en la ultima hoja a recorrer, es decir, que necesito recorrer todos los investigadores y todas las relaciones, ya que el resultado a buscar se encuentra como hijo del ultimo investigador. Sumado a esto la mayor cantidad de relaciones definidad va a ser cuando hay relaciones entre mismos investigadores(irene irene) y relaciones mutuas (irene juan / juan irene).
\section{Conclusiones}

Este problema se presento como algo sencillo de hacerlo al principio, aunque nos topamos con la dificultad de tratar de implementar una idea que no cumplia con los requerimientos de complejidad , pero luego pudimos hacer un algoritmo basado en una de las claces teoricas sobre grafos, y como recorrer el mismo.

Ademas de confirmarnos que la complejidad pedida se cumplia en cada caso con la calculada en base a nuestro algoritmo, esto fue mas en el caso de pensar en el peor caso y compararlo con la complejidad teorica.
